// Copyright (c) 2010 SuccessFactors, Inc.
// All rights reserved.
//
// Redistribution and use in source and binary forms, with or without
// modification, are permitted provided that the following conditions
// are met:
//
//     * Redistributions of source code must retain the above
//       copyright notice, this list of conditions and the following
//       disclaimer.
//
//     * Redistributions in binary form must reproduce the above
//       copyright notice, this list of conditions and the following
//       disclaimer in the documentation and/or other materials
//       provided with the distribution.
//
//     * Neither the name of the SuccessFactors, Inc. nor the names of
//       its contributors may be used to endorse or promote products
//       derived from this software without specific prior written
//       permission.
//
// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
// FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
// COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT,
// INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
// (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
// SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
// HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
// STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
// ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
// OF THE POSSIBILITY OF SUCH DAMAGE.

package org.owasp.jxt;

import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.ConcurrentMap;
import java.util.concurrent.atomic.AtomicLong;

/**
 * QuickCache -- a quick-to-use unbounded lazy-loading cache designed
 * to allow for high concurrency rates.  Note: this is also a quick
 * and dirty solution.  A better solution would abstract out the
 * resolution of objects into a separate interface, and allow room for
 * additional QuickCache subclasses to provide different caching
 * behaviors.
 *
 * @author Jeffrey Ichnowski
 * @version $Revision: 8 $
 */
public abstract class QuickCache<K,V> {

    /**
     * Using this value (-1L) as a stale check interval will cause the
     * QuickCache instance to never do stale checks.
     */
    public static final long NO_STALE_CHECKS = -1L;

    /**
     * Using this value (0L) as a stale check interval will cause the
     * QuickCache instance to check staleness on every access.
     */
    public static final long ALWAYS_STALE_CHECK = 0L;

    /**
     * Contains the cache key->value mappings.
     */
    private final ConcurrentMap<K,ValueHolder<V>> _map;

    /**
     * The interval between stale checks.
     */
    final long _intervalBetweenStaleChecks;

    /**
     * Constructs a cache that does not do stale checks.
     */
    public QuickCache() {
        this(-1L);
    }

    /**
     * Constructs a cache that checks at the specified interval if a
     * cache entry is stale.
     *
     * @param intervalBetweenStaleChecks the number of milliseconds to
     * wait between checks for staleness.  Specifying <code>-1L</code>
     * will disable stale checks.  Specifying <code>0</code> will
     * check at every reference.
     */
    public QuickCache(long intervalBetweenStaleChecks) {
        if (intervalBetweenStaleChecks < -1L) {
            throw new IllegalArgumentException(
                "intervalBetweenStaleChecks must be -1, 0, or positive");
        }
        _intervalBetweenStaleChecks = intervalBetweenStaleChecks;
        _map = new ConcurrentHashMap<K,ValueHolder<V>>();
    }

    /**
     * Returns the current size of the cache (number of elements
     * contained).  Note: this may be off by a little bit as objects
     * being initialized (resolved) may be counted in the total
     * returned.
     *
     * @return the size of the cache
     */
    public final int size() {
        return _map.size();
    }

    /**
     * Returns the value associated with a key.  On the first (and
     * only the first) invocation with a particular key, the value is
     * resolved via the <code>resolve(key)</code> method.
     *
     * <p>This method may block on first invocation with a new key.
     *
     * @param key the key to look up.
     * @return the value resolved
     */
    public final V get(K key) {
        for (;;) {
            ValueHolder<V> value = _map.get(key);

            if (null == value) {
                Initializer initializer = new Initializer(key);
                value = _map.putIfAbsent(key, initializer);

                if (null == value) {
                    value = initializer;
                }
            }

            try {
                return value.get();
            } catch (StaleValueException e) {
                // This exception is thrown if another thread tried to
                // init the item, failed, and thus removed the
                // initalizer from the map.

                // try to init again in the current landscape

                // this could be argued as an example of using
                // exceptions for flow control (an anti-pattern), but
                // since it's an exception condition that would cause
                // a reinit to be tried, it seems somewhat okay.
                e = null;
            }
        }
    }

    /**
     * Resolves a value associated with a key.  Sub-classes implement
     * this method to provide different cache resolution.  If
     * <code>null</code> is returned, it is cached as the return
     * value.
     *
     * <p>This method should never throw an exception.  (If it does,
     * it will be passed on to the caller for only the first
     * invocation of get.  Subsequent invocations will get null for
     * the same key.)
     *
     * @param key the key to resolve
     * @return the value resolved.  null is allowed.
     */
    protected abstract V resolve(K key);

    /**
     * Checks if the entry is stale.  Stale entries will be removed
     * from the cache and replaced with a fresh resolve.  If this
     * method returns <code>true</code>, resolve will be called with
     * the same key immediately.
     *
     * @param key the cache key to check
     * @param value the value to check
     * @return <code>true</code> if the value is stale and should be
     * resolved again.  The default implementation always returns
     * <code>false</code>.
     */
    protected boolean isStale(K key, V value) {
        return false;
    }

    /**
     * Internal interface used to wrap logic around getting the
     * current value.
     */
    private static interface ValueHolder<V> {
        V get();
    }

    /**
     * An initialized stable value.  This value will always return the
     * same result and will never perform a stale check.
     */
    private static class StableValue<V> implements ValueHolder<V> {
        private V _value;

        StableValue(V value) {
            _value = value;
        }

        public V get() {
            return _value;
        }
    }

    /**
     * An initialized value that will perform a stale check at a
     * specified interval.
     */
    private class StaleCheckValue implements ValueHolder<V> {
        private final K _key;
        private final V _value;
        private final AtomicLong _nextCheck;

        StaleCheckValue(K key, V value) {
            _key = key;
            _value = value;
            _nextCheck = new AtomicLong(System.currentTimeMillis() + _intervalBetweenStaleChecks);
        }

        public V get() {
            long nextCheck = _nextCheck.get();

            // we use compareAndSet to ensure that only one stale
            // check happens at a time.  During the stale check (if it
            // is long running), other threads will get the old value.

            if (System.currentTimeMillis() >= nextCheck &&
                _nextCheck.compareAndSet(nextCheck, Long.MAX_VALUE))
            {
                if (isStale(_key, _value)) {
                    _map.remove(_key, this);
                    throw new StaleValueException();
                }

                // After the stale check, the next interval is
                // calculated and stored.  This will unset
                // Long.MAX_VALUE and allow subsequent threads to
                // attempt stale checks.
                _nextCheck.set(System.currentTimeMillis() + _intervalBetweenStaleChecks);
            }

            return _value;
        }
    }

    /**
     * This is an uninitialized value holder that will resolve the
     * value and replace itself in the cache's map with either the
     * StableValue or StaleCheckValue after successful resolution.
     * While a value is being resolved other threads will block on the
     * <code>get()</code> call waiting for it to be resolved.
     */
    private class Initializer implements ValueHolder<V> {
        private final K _key;
        private V _value;
        private boolean _resolved;

        Initializer(K key) {
            _key = key;
        }

        public synchronized V get() {
            if (!_resolved) {

                // first check that the key maps to the entry for this
                // value holder.  If it does not, then another thread
                // has already tried to initialize the cache entry and
                // failed.  The result is that the Initializer for
                // that key (this object) would be removed from the
                // map (since it could be a DOS attack to store unused
                // initializer entries for all attempted lookups.

                if (_map.get(_key) != this) {
                    throw new StaleValueException();
                }

                try {
                    // attempt resolution.  If resolve throws an
                    // unchecked exception or an error, then it will
                    // be percolated up to the caller
                    // (no-catch-rethrow needed).  We simply check if
                    // _resolved == true.  If it is not, then it means
                    // resolve did not return normally.  This also
                    // allows null to be a valid resolution.
                    _value = resolve(_key);
                    _resolved = true;
                } finally {
                    if (!_resolved) {
                        // _resolved will be false if value was not
                        // set because of an exception.  Since we
                        // aren't tracking if any threads are waiting
                        // for this initializer, we remove this
                        // Initializer object to allow it to be GC'd
                        // and the map size to remain unchanged.
                        _map.remove(_key, this);
                    } else {

                        // The value was resolved successfully,
                        // replace the entry in the map with a new one
                        // that will not synchronized on each get
                        // call.

                        ValueHolder<V> newValue = _intervalBetweenStaleChecks == -1L ?
                            new StableValue<V>(_value) :
                            new StaleCheckValue(_key, _value);

                        _map.replace(_key, this, newValue);
                    }
                }
            }

            return _value;
        }
    }

    /**
     * Exception thrown by ValueHolder.get() method if the value is
     * stale and was removed from the map.  This instructs the cache's
     * get method to try again.  It is not meant to be thrown by
     * anything other than the internal ValueHolder implementations.
     */
    private static class StaleValueException extends RuntimeException {
    }
} // QuickCache
